package com.gxc.linkedList;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 3148. 矩阵中的最大得分

 * 给你一个由 正整数 组成、大小为 m x n 的矩阵 grid。你可以从矩阵中的任一单元格移动到另一个位于正下方或正右侧的任意单元格（不必相邻）。从值为 c1 的单元格移动到值为 c2 的单元格的得分为 c2 - c1 。
 *
 * 你可以从 任一 单元格开始，并且必须至少移动一次。
 *
 * 返回你能得到的 最大 总得分。
 */
public class MaxScore {

    public static void main(String[] args) {
        System.out.println(handle(new int[][]{
                {9,5,7,3},{8,9,6,1},{6,7,14,3},{2,5,3,1}
        }));

        List<List<Integer>> grid = new ArrayList<>();
        grid.add(Arrays.asList(9,5,7,3));
        grid.add(Arrays.asList(8,9,6,1));
        grid.add(Arrays.asList(6,7,14,3));
        grid.add(Arrays.asList(2,5,3,1));
        System.out.println(maxScore(grid));

        System.out.println(handle(new int[][]{
                {4,3,2},{3,2,1}
        }));
    }

    public static int handle(List<List<Integer>> grid) {
        int[][] tab = new int[grid.size()][grid.get(0).size()];

        for (int i = 0; i < grid.size(); i++) {
            List<Integer> list = grid.get(i);
            for (int j = 0; j < list.size(); j++) {
                tab[i][j] = list.get(j);
            }
        }
        return handle(tab);
    }

    public static int handle(int[][] tab) {
        /**
         * 从 0,0 出发 到 i,j  获取的最大得分（可跳过某些节点）
         */
        int[][] dp = new int[tab.length][tab[0].length];
        dp[0][0] = 0;
        int max = Integer.MIN_VALUE;
        for (int i = 1; i < dp.length; i++) {
            int sum = Math.max(dp[i - 1][0], 0);
            dp[i][0] = sum + tab[i][0] - tab[i-1][0];
            max = Math.max(max, dp[i][0]);
        }
        for (int i = 1; i < dp[0].length; i++) {
            int sum = Math.max(dp[0][i-1], 0);
            dp[0][i] = sum + tab[0][i] - tab[0][i-1];
            max = Math.max(max, dp[0][i]);
        }

        for (int i = 1; i < tab.length; i++) {
            for (int j = 1; j < tab[i].length; j++) {
                int sum1 = tab[i][j] - tab[i-1][j] + Math.max(dp[i-1][j], 0);
                int sum2 = tab[i][j] - tab[i][j-1] + Math.max(dp[i][j-1], 0);
                dp[i][j] = Math.max(sum1, sum2);
                max = Math.max(max, dp[i][j]);
            }
        }
        return max;
    }

    public static int maxScore(List<List<Integer>> grid) {
        int m = grid.size(), n = grid.get(0).size();
        int[][] prerow = new int[m][n];
        int[][] precol = new int[m][n];
        int[][] f = new int[m][n];
        for (int i = 0; i < m; ++i) {
            Arrays.fill(f[i], Integer.MIN_VALUE);
        }
        int ans = Integer.MIN_VALUE;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (i > 0) {
                    f[i][j] = Math.max(f[i][j], grid.get(i).get(j) + precol[i - 1][j]);
                }
                if (j > 0) {
                    f[i][j] = Math.max(f[i][j], grid.get(i).get(j) + prerow[i][j - 1]);
                }
                ans = Math.max(ans, f[i][j]);
                prerow[i][j] = precol[i][j] = Math.max(f[i][j], 0) - grid.get(i).get(j);
                if (i > 0) {
                    precol[i][j] = Math.max(precol[i][j], precol[i - 1][j]);
                }
                if (j > 0) {
                    prerow[i][j] = Math.max(prerow[i][j], prerow[i][j - 1]);
                }
            }
        }
        return ans;
    }

    class Solution2 {
        public int maxScore(List<List<Integer>> grid) {
            int m = grid.size(), n = grid.get(0).size();
            int[] precol = new int[n];
            Arrays.fill(precol, Integer.MIN_VALUE);
            int ans = Integer.MIN_VALUE;
            for (int i = 0; i < m; ++i) {
                int prerow = Integer.MIN_VALUE;
                for (int j = 0; j < n; ++j) {
                    int f = Integer.MIN_VALUE;
                    if (i > 0) {
                        f = Math.max(f, grid.get(i).get(j) + precol[j]);
                    }
                    if (j > 0) {
                        f = Math.max(f, grid.get(i).get(j) + prerow);
                    }
                    ans = Math.max(ans, f);
                    precol[j] = Math.max(precol[j], Math.max(f, 0) - grid.get(i).get(j));
                    prerow = Math.max(prerow, Math.max(f, 0) - grid.get(i).get(j));
                }
            }
            return ans;
        }
    }

    /**
     * 二维前缀和
     *
     *
     * premin 记录当前的最小值
     */
    class Solution3 {
        public int maxScore(List<List<Integer>> grid) {
            int m = grid.size(), n = grid.get(0).size();
            int[][] premin = new int[m][n];
            for (int i = 0; i < m; ++i) {
                Arrays.fill(premin[i], Integer.MAX_VALUE);
            }
            int ans = Integer.MIN_VALUE;
            for (int i = 0; i < m; ++i) {
                for (int j = 0; j < n; ++j) {
                    int pre = Integer.MAX_VALUE;
                    if (i > 0) {
                        pre = Math.min(pre, premin[i - 1][j]);
                    }
                    if (j > 0) {
                        pre = Math.min(pre, premin[i][j - 1]);
                    }
                    // i = j = 0 时没有转移
                    if (i + j > 0) {
                        ans = Math.max(ans, grid.get(i).get(j) - pre);
                    }
                    premin[i][j] = Math.min(pre, grid.get(i).get(j));
                }
            }
            return ans;
        }
    }

    class Solution4 {
        public int maxScore(List<List<Integer>> grid) {
            int m = grid.size(), n = grid.get(0).size();
            int[][] premin = new int[2][n];
            for (int i = 0; i < 2; ++i) {
                Arrays.fill(premin[i], Integer.MAX_VALUE);
            }
            int ans = Integer.MIN_VALUE;
            for (int i = 0; i < m; ++i) {
                Arrays.fill(premin[i & 1], Integer.MAX_VALUE);
                for (int j = 0; j < n; ++j) {
                    int pre = Integer.MAX_VALUE;
                    if (i > 0) {
                        pre = Math.min(pre, premin[(i - 1) & 1][j]);
                    }
                    if (j > 0) {
                        pre = Math.min(pre, premin[i & 1][j - 1]);
                    }
                    // i = j = 0 时没有转移
                    if (i + j > 0) {
                        ans = Math.max(ans, grid.get(i).get(j) - pre);
                    }
                    premin[i & 1][j] = Math.min(pre, grid.get(i).get(j));
                }
            }
            return ans;
        }
    }

}
